#include<iostream>
using namespace std;

//节点类
template<class T>
class node
{
public:
    node();
    node(const T &value);
    ~node();

public:
    node<T> *prev;
    node<T> *next;
    T data;
};

template<class T>
node<T>::node() : prev(nullptr), next(nullptr), data()
{
}

template<class T>
node<T>::node(const T &value)
{  
    prev = nullptr;
    next = nullptr;
    data = value;
}

template<class T>
node<T>::~node()
{
}


//双向循环链表类
template<class T>
class dlist
{
public:
    dlist();
    ~dlist();

    //末尾插入一个节点
    void push_back(const T &value);
    //头部插入一个节点
    void push_front(const T &value);
    //判断列表是否为空
    bool empty();
    //清空列表元素
    void clear();
    //获取第一个元素的引用
    T &front();
    //获取最后一个元素的引用
    T &back();
    //删除最后一个元素
    void pop_back();
    //删除第一个元素
    void pop_front();
    //在指定位置插入一个元素
    void insert(int index,T value);
    //删除指定元素
    void remove(T value);
    //获取列表元素个数
    int size();
    //遍历列表元素
    void show();
    
private:
    node<T> *head;
};

template<class T>
dlist<T>::dlist()
{
    head = new node<T>();//构造一个虚拟头结点
    //实现双向循环，也就是让自己指向自己
    head->next = head;
    head->prev = head;
}

template<class T>
dlist<T>::~dlist()
{
    if(head->next == head)
    {}
    else
    {
        node<T> *_node = head->next;
        while(_node != head)
        {
            node<T> *next_node = _node->next;
            delete  _node;
            _node = next_node;
        }
        head->next = head;
        head->prev = head;
    }
    delete head;
    head = nullptr;
}

template<class T>
void dlist<T>::push_back(const T &value)
{
    //构造一个节点
    node<T> *_node = new node<T>(value);

    //插入节点，判断是否为第一个节点
    if(head->next == head)//头结点下一个还是头结点即为插入第一个节点
    {
        head->next = _node;
        _node->prev = head;
        _node->next = head;
        head->prev = _node;
    }
    else
    {
        node<T> *tail = head->prev;
        head->prev = _node;
        tail->next = _node;
        _node->prev = tail;
        _node->next = head;
    }
}

template<class T>
void dlist<T>::push_front(const T &value)
{
    //构造一个节点
    node<T> *_node = new node<T>(value);

    //插入节点，判断是否为第一个节点
    if(head->next == head)//头结点下一个还是头结点即为插入第一个节点
    {
        head->next = _node;
        _node->prev = head;
        _node->next = head;
        head->prev = _node;
    }
    else
    {
        node<T> *next_node = head->next;
        head->next = _node;
        next_node->prev = _node;
        _node->prev = head;
        _node->next = next_node;
    }
}

template<class T>
bool dlist<T>::empty()
{
    if(head->next == head)
        return true;
    else
        return false;
}

template<class T>
void dlist<T>::clear()
{
    if(head->next == head)
    {
        cout << "当前列表仅有一个头结点，无数据！" << endl;
    }
    else
    {
        node<T> *_node = head->next;
        while(_node != head)
        {
            node<T> *next_node = _node->next;
            delete  _node;
            _node = next_node;
        }
        head->next = head;
        head->prev = head;
    }
}

template<class T>
T &dlist<T>::front()
{
    if(empty())
        cout << "当前列表仅有一个头结点，无数据！" << endl;
    return head->next->data;
        
}

template<class T>
T &dlist<T>::back()
{
    if(empty())
        cout << "当前列表仅有一个头结点，无数据！" << endl;
    return head->prev->data;
}

template<class T>
void dlist<T>::pop_back()
{
    if(!empty())
    {
        node<T> *_node = head->prev->prev;
        head->prev = _node;
        _node->next = head;
    }
}

template<class T>
void dlist<T>::pop_front()
{
    if(!empty())
    {
        node<T> *_node = head->next->next;
        head->next = _node;
        _node->prev = head;
    }
}

template<class T>
void dlist<T>::insert(int index,T value)
{
    if(index <= size()+1 && index >= 1)
    {
        int i = 1;
        //构造一个节点
        node<T> *_node = new node<T>(value);
        if(index == 1)
        {
            push_front(value);
        }
        else if(index == size()+1)
        {
            push_back(value);
        }
        else
        {
            node<T> *node_next = head->next;
            while(node_next != head)
            {
                if(i==index)
                {
                    break;
                }
                node_next = node_next->next;
                i++;
            }
            node_next->prev->next = _node;
            _node->prev = node_next->prev;
            _node->next = node_next;
            node_next->prev = _node;
        }
    }
}

template<class T>
void dlist<T>::remove(T value)
{
    node<T> *node_next = head->next;
    while(node_next != head)
    {
        if(value == node_next->data)
        {
            node_next->prev->next = node_next->next;
            node_next->next->prev = node_next->prev;
            break;
        }
        node_next = node_next->next;
    }
}

template<class T>
int dlist<T>::size()
{
    int num =  0;
    if(head->next == head)
    {
        return num;
    }
    else
    {
        node<T> *_node = head->next;
        while(_node != head)
        {
            _node = _node->next;
            num ++;
        }
        return num;
    }
}

template<class T>
void dlist<T>::show()
{
    if(head->next == head)
    {
        cout << "当前列表仅有一个头结点，无数据！" << endl;
    }
    else
    {
        node<T> *_node = head->next;
        cout << "当前列表数据：";
        while(_node != head)
        {
            cout << _node->data << " ";
            _node = _node->next;
        } 
        cout << endl;
    }
}

int main()
{   
    dlist<int> b;
    cout << "利用push_back插入1,2,3" << endl;
    b.push_back(1);
    b.push_back(2);
    b.push_back(3);
    b.show();
    cout << "当前列表长度(size)：" << b.size() << endl;
    cout << "利用push_front插入4" << endl;
    b.push_front(4);
    b.show();
    cout << "当前列表长度：" << b.size() << endl;
    cout << "利用insert(1,10)插入" << endl;
    b.insert(1,10);
    b.show();
    cout << "利用insert(6,11)插入" << endl;
    b.insert(6,11);
    b.show();
    cout << "利用insert(2,99)插入" << endl;
    b.insert(2,99);
    b.show();
    cout << "利用front查找第一个元素:" << b.front() << endl;
    cout << "利用back查找最后一个元素:" << b.back() << endl;
    cout << "利用pop_front删除第一个元素" << endl;
    b.pop_front();
    b.show();
    cout << "利用pop_front删除最后一个元素" << endl;
    b.pop_back();
    b.show();
    cout << "利用remove删除第一个值为2的元素:" << endl;
    b.remove(2);
    b.show();
    cout << "当前列表长度(size):" << b.size() << endl;
    cout << "链表是否为空(empty)(1为空,0为非空):"<< b.empty() << endl;
    cout << "清除链表所有元素(clear)" << endl;
    b.clear();
    cout << "当前列表长度(size):" << b.size() << endl;
    cout << "链表是否为空(empty)(1为空,0为非空):"<< b.empty() << endl;

    return 0;
}